package com.linyaonan.leetcode.hard._42;

import java.util.Arrays;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
 * <p>
 * 示例:
 * <p>
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 *
 * @author: Lin
 * @date: 2020/4/4
 */
public class Trap {
    /**
     * 逐行分析，最后一行会超时
     *
     * @param height
     * @return
     */
    public int trapOld(int[] height) {
        // 找出最小值
        int min = Integer.MAX_VALUE;
        for (int i : height) {
            if (i <= min) {
                min = Math.min(i, min);
            }
        }
        if (min != 0) {
            // 水平线修改到0
            for (int i = 0; i < height.length; i++) {
                height[i] -= min;
            }
        }

        boolean isDone = false;
        int allCount = 0;
        while (!isDone) {
            boolean isStart = false;
            // 一次循环的总水池数
            int count = 0;
            // 找到开始位置
            int temp = 0;
            // 统计0的个数
            int zeroCount = 0;
            for (int i = 0; i < height.length; i++) {
                int num = height[i];
                if (!isStart && num > 0) {
                    isStart = true;
                    height[i]--;
                    continue;
                }
                // 找到结尾
                if (isStart && num > 0) {
                    count += temp;
                    // temp重置
                    temp = 0;
                    height[i]--;
                    continue;
                }
                if (num == 0) {
                    zeroCount++;
                }
                // 需要统计进去
                if (isStart && num == 0) {
                    temp++;
                }
            }
            allCount += count;
            if (zeroCount == height.length) {
                isDone = true;
            }
        }

        return allCount;
    }

    public int trap(int[] height) {
        int sum = 0;
        int[] max_left = new int[height.length];
        int[] max_right = new int[height.length];
        // 左边i位置最高统计
        for (int i = 1; i < height.length - 1; i++) {
            max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
        }
        // 右边i位置最高统计
        for (int i = height.length - 2; i >= 0; i--) {
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            // 左右最高柱子取较小
            int min = Math.min(max_left[i], max_right[i]);
            // 当大于当前柱子才有统计必要
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }

    /**
     * 不需要使用动态规划处理，通过观察可以发现
     * 当i位置能存储的水量等于i左边，与i右边最高的柱子的相对低者决定
     * 拿这个数组分析：
     * [0,1,0,2,1,0,1,3,2,1,2,1]
     *
     * 0：左边没有比他高的，右边有一个1比他高，所以存储为0
     * 1：左边没有比他高的，所以为0
     * 0：左边1比他高，右边2比他高，取数值较小的，所以存储1-0
     * 2：左边没有比他高的，所以为0
     * 1：左边2比他高，右边3比他高，取数值小的，所以存储2-1
     *
     * 依次类推，所以从左边看找出比当前位置高的柱子的数值存储下来
     * 从右边看找出比当前位置高的柱子数值存储下来，然后再遍历原始数据找到左右均比自己大，并且取出左右相对低的高度减去自身高度
     *
     * @param height
     * @return
     */
    public int trap2(int[] height) {
        // 1. 异常边界
        if (height == null || height.length == 0 || height.length == 1) {
            return 0;
        }
        int[] lMax = new int[height.length];
        int lMaxNum = height[0];
        for (int i = 0; i < height.length; i++) {
            lMaxNum = Math.max(lMaxNum, height[i]);
            lMax[i] = lMaxNum;
        }
        int[] rMax = new int[height.length];
        int rMaxNum = height[height.length - 1];
        for (int i = height.length - 1; i >= 0; i--) {
            rMaxNum = Math.max(rMaxNum, height[i]);
            rMax[i] = rMaxNum;
        }
        int num = 0;
        for (int i = 0; i < height.length; i++) {
            if (lMax[i] > height[i] && rMax[i] > height[i]) {
                num += Math.min(lMax[i], rMax[i]) - height[i];
            }
        }

        return num;

    }
}
